#include<iostream>
#include<fstream>
#include<string>

using namespace std;

template<class T>
class ArrayNode
{
public:
    T item;
    int num;
    ArrayNode();
    ~ArrayNode();
};

template<class T>
ArrayNode<T>::ArrayNode()
{
    
}
template<class T>
ArrayNode<T>::~ArrayNode()
{

}


template<class T>
class VariousSort
{
public:
    ArrayNode<T> *itemArray;
    int length;
    VariousSort(int);
    ~VariousSort();
    void InsertNum(string fileName)
    {
        fstream file;
        file.open("VariousSort.txt", ios::in);

        for(int i = 0;i<length;i++)
        {
            T temp;
            file >> temp;
            itemArray[i].item = temp;
            file>>itemArray[i].num;
        }
        file.close();
    }
    void DirectInsertSort();
    void HalfInsertSort();
    void ShellSort();
    void BubbleSort();
    void QuickSort();
    void ChooseSort();
    void PrintArray(ArrayNode<T> * array)
    {
        for(int i = 0;i<length;i++)
        {
            cout<<(array+i)->item<<"/"<<(array+i)->num<<" ";
        }
        cout<<endl;
    }
};

template<class T>
VariousSort<T>::VariousSort(int length)
{
    itemArray = new ArrayNode<T>[length];
    this->length = length;  
}
template<class T>
void VariousSort<T>::DirectInsertSort()
{
    cout<<"直接插入排序"<<endl;
    ArrayNode<T> tempArray[length];
    for(int i = 0;i<length;i++)
    {
        tempArray[i] = itemArray[i];
    }
    for(int i = 1;i<length;i++)
    {
        ArrayNode<T> TempRecord = tempArray[i];
        int j = i-1;
        while((j>=0)&&(TempRecord.num<tempArray[j].num))
        {
            tempArray[j+1] = tempArray[j];
            j--;
        }
        tempArray[j+1] = TempRecord;
    }
    PrintArray(tempArray);
}

template<class T>
void VariousSort<T>::HalfInsertSort()
{
    cout << "折半插入排序" << endl;
    ArrayNode<T> tempArray[length];
    for(int i = 0;i<length;i++)
    {
        tempArray[i] = itemArray[i];
    }
    for (int i = 1; i < length; i++)
    {
        int left = 0, right = i - 1;
        ArrayNode<T> TempRecord = tempArray[i];
        
        while(left<=right)
        {
            int middle = (left + right) / 2;
            if(TempRecord.num<tempArray[middle].num)
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        }
        for (int j = i - 1;j>=left;j--)
        {
            tempArray[j + 1] = tempArray[j];
        }
        tempArray[left] = TempRecord;
        
    }
    PrintArray(tempArray);
}

template<class T>
void VariousSort<T>::ShellSort()
{
    cout << "希尔排序" << endl;

    ArrayNode<T> tempArray[length];
    for(int i = 0;i<length;i++)
    {
        tempArray[i] = itemArray[i];
    }

    ArrayNode<T> TempRecord;
    int gap = length / 2;
    while(gap!=0)
    {
        //cout << "gap = " << gap << endl;
        for (int i = gap; i < length; i += gap)
        {
            //cout << "i = " << i << endl;
            ArrayNode<T> TempRecord = tempArray[i];
            int j = i - gap;
            while ((j >= 0) && (TempRecord.num < tempArray[j].num))
            {
                tempArray[j + gap] = tempArray[j];
                j-=gap;
            }
            tempArray[j + gap] = TempRecord;
            //PrintArray(tempArray);
        }
        gap /= 2;
    }
    PrintArray(tempArray);
}

template<class T>
void VariousSort<T>::BubbleSort()
{
    cout << "冒泡排序" << endl;
    ArrayNode<T> tempArray[length];
    
    for (int i = 0; i < length; i++)
    {
        tempArray[i] = itemArray[i];
    }
    
    for (int i = 0; i < length; i++)
    {
        
        for (int j = length-1; j > i;j--)
        {
            if(tempArray[j-1].num>tempArray[j].num)
            {
                ArrayNode<T> tempRecord = tempArray[j - 1];
                tempArray[j - 1] = tempArray[j];
                tempArray[j] = tempRecord;
            }
        }
    }
    PrintArray(tempArray);
}
template<class T>
VariousSort<T>::~VariousSort()
{
    delete[] itemArray;
}



int main()
{
    VariousSort<char> * temp = new VariousSort<char>(6);
    temp->InsertNum("VariousSort.txt");
    temp->DirectInsertSort();
    temp->HalfInsertSort();
    temp->ShellSort();
    temp->BubbleSort();
    delete temp;
}